package com.atguigu.KMP;

/**
 * @author tbwtbw
 * @create 2021-11-25 16:25
 */
public class KMP {
    public static void main(String[] args) {
        String str2 = "aabaaf";
        String str1 = "aabaacaabaaf";
        int[] next = getNext(str1);
        System.out.println(kmp(str1, str2, next));
    }

    public static int kmp(String str1,String str2,int[] next){

        for (int i = 0,j = 0; i < str1.length(); i++){
            while(j > 0 && str1.charAt(i) != str2.charAt(j)) {//这里的next数组就是部分匹配值表，next[i]表示下标为0-i的字符串的
                //最大的相同前后缀数，所以失配的时候j = next[j-1] 意思是让 j 滑到 前面 j（下标从0开始，实际上有j+1个元素） 个字符组成的字符串
                //的最大公共前后缀的下一个位置，这个新指向的字符再与 i 比较
                j = next[j-1];
            }
            if (str1.charAt(i) == str2.charAt(j)){
                j++;
            }
            if (j == str2.length())
                return i + 1 - j;
        }
        return -1;
    }

    public static int[] getNext(String substring){
        int[] next = new int[substring.length()];
        next[0] = 0;
        // i 是后缀的最后一个字母 ， j 是前缀的最后一个字母 , 只要substring.charAt(i) != substring.charAt(j)就说明最大公共前后缀匹配不上，
        //那么就找次大的，次大的怎么取呢，就是 j = next[j-1].dest[i]与dest[j]不匹配时，如果j不为0，那么dest[i-j]~dest[i-1]肯定和dest[0]~dest[j-1]匹配，
       for(int i = 1,j = 0; i < substring.length(); i++){
           while (j > 0 && substring.charAt(i) != substring.charAt(j)){
               j = next[j-1];
           }
           if (substring.charAt(i) == substring.charAt(j)){
               j++;
           }
           next[i] = j;
       }
       return next;
    }
}
